package 题目集.二分;

import java.util.Arrays;
import java.util.Random;

import org.junit.Test;

/**
 * 做法：记录每个数的下标，根据大小排序，相同则按下标排序。 当查找区间内某个数出现的个数时，先二分找到这个数，再二分查找这个区间内的下标。
 */
public class ch12_获取区间内指定数的个数 {
	static class Search {
		int[][] index;

		public Search(int[] src) {
			index = new int[src.length][2];
			for (int i = 0; i < src.length; i++) {
				index[i][0] = src[i];
				index[i][1] = i;
			}
			Arrays.sort(index, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (a[1] - b[1]));
		}

		public int count(int l, int r, int x) {
			int first = first(x); // 数值x第一次出现的位置
			int last = last(x); // 数字x最后一次出现的位置
			if (first == -1 || last == -1 || index[first][1] > r || index[last][1] < l)
				return 0;
			int li = left(first, last, l); // 出现位置中，在l右侧的
			int ri = right(first, last, r); // 出现位置中，在r左侧的
			return ri - li + 1;
		}

		public int left(int l, int r, int i) {
			while (l <= r) {
				int m = l + r >> 1;
				if (index[m][1] < i) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			return l;
		}

		public int right(int l, int r, int i) {
			while (l <= r) {
				int m = l + r >> 1;
				if (index[m][1] <= i) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			return r;
		}

		private int first(int x) {
			int l = 0, r = index.length - 1;
			while (l <= r) {
				int m = l + r >> 1;
				if (index[m][0] < x) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			if (l < index.length && index[l][0] == x) {
				return l;
			}
			return -1;
		}

		private int last(int x) {
			int l = 0, r = index.length - 1;
			while (l <= r) {
				int m = l + r >> 1;
				if (index[m][0] <= x) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			if (r >= 0 && index[r][0] == x) {
				return r;
			}
			return -1;
		}
	}

	@Test
	public void test() {
		int count=(int) 1e5;
		int maxn=(int) 1e3;
		int maxv=(int) 1e2;
		int ops=100;
		for(int i=1;i<=count;i++) {
			compare(maxn,maxv,ops);
			if(i%(int)1e3==0) {
				System.out.println(i+"组测试完成.");
			}
		}
	}

	Random rd = new Random();

	public void compare(int maxn,int maxv,int opCnt) {
		int n = rd.nextInt(maxn) + 1;
		int[] src = new int[n];
		for (int i = 0; i < n; i++) {
			src[i] = rd.nextInt(maxv);
		}
		Ans ansTset=new Ans(src.clone());
		Search search=new Search(src.clone());
		for(int i=0;i<opCnt;i++) {
			int a=rd.nextInt(n);
			int b=rd.nextInt(n);
			int x=rd.nextInt(maxv);
			int l=Math.min(a, b);
			int r=Math.max(a, b);
			int ans=ansTset.count(l, r, x);
			int s=search.count(l, r, x);
			if(ans!=s) {
				System.out.println("error");
				search.count(l, r, x);
			}
		}
	}

	static class Ans {
		int[] src;

		public Ans(int[] src) {
			this.src = src;
		}

		public int count(int l, int r, int x) {
			int cnt = 0;
			while (l <= r) {
				if (src[l++] == x) {
					cnt++;
				}
			}
			return cnt;
		}
	}
}
